/*
 * @lc app=leetcode.cn id=220 lang=cpp
 *
 * [220] 存在重复元素 III
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    // 桶排序啊，把整个整数轴分割成宽度t的段，
    // 看k长度滑窗里数落到同段/相邻段
    // 才有可能间距小于t

    int getID(int x, long w) {
        return x < 0 ? (x + 1ll) / w - 1 : x / w;
    }

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        unordered_map<int, int> mp;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            long x = nums[i];
            int id = getID(x, t + 1ll);
            if (mp.count(id)) {
                return true;
            }
            // 标准库的hash自带的count查询此hash结果链表长度=>桶内数量
            if (mp.count(id - 1) and abs(x - mp[id - 1]) <= t) {
                return true;
            }
            if (mp.count(id + 1) and abs(x - mp[id + 1]) <= t) {
                return true;
            }
            mp[id] = x;
            if (i >= k) {
                mp.erase(getID(nums[i - k], t + 1ll));
            }
        }
        return false;
    }
};

// @lc code=end

// [1, 2, 3, 4, 5, 6] 2
//  0  1  2  3  4  5
// i-k-1    i=3

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        set<int> sildingWindowSet;
        for (int i = 0; i < n; i++) {
            auto iter = sildingWindowSet.lower_bound(max(nums[i], INT_MIN + t) - t);
            if (iter != sildingWindowSet.end() && *iter <= min(nums[i], INT_MAX - t) + t) {
                return true;
            }
            sildingWindowSet.insert(nums[i]);
            if (i >= k) {
                sildingWindowSet.erase(nums[i - k]);
            }
        }
        return false;
    }
};

// 似乎没必要什么都往区间上靠。。。
// 求值所处range的max泛用，但用差分会超时

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        // <num, occurence_times>
        std::unordered_map<int, int> hashNum;
        // <num, diff operation>
        std::map<int, int> rangeMap;

        int n = nums.size();
        for (int i=0;i<n;++i){
            if (i-indexDiff-1 >= 0){
                // remove old num and old range
                auto iter = hashNum.find(nums[i-indexDiff-1]);
                int oldNum = nums[i-indexDiff-1];
                // +- valueDiff
                if (iter->second == 1){
                    hashNum.erase(iter);
                }else{
                    iter->second -= 1;
                }

                // clear range ~
                rangeMap[oldNum - valueDiff]--;
                rangeMap[oldNum + valueDiff + 1]++;

                // remove useless operation (diff = 0)
                auto iterDel = rangeMap.find(oldNum - valueDiff);
                if (iterDel->second == 0){rangeMap.erase(iterDel);}
                iterDel = rangeMap.find(oldNum + valueDiff + 1);
                if (iterDel->second == 0){rangeMap.erase(iterDel);}
            }

            int num = nums[i];
            int sum = 0;
            // search num in range, if found return true
            auto iter = rangeMap.upper_bound(nums[i]);

            // min < num <= max
            for (auto i=rangeMap.begin();i != iter;++i){
                sum += i->second;
            }
            if (iter->first == nums[i]){
                sum += iter->second;
            }

            // check operation sum > 0
            if (sum > 0){
                return true;
            }

            // if not, add it to hashNum and update range
            hashNum[num]++;
            rangeMap[num - valueDiff]++;
            rangeMap[num + valueDiff + 1]--;
        }
        return false;
    }
};
